﻿//using System;
//using System.Collections.Generic;
//using System.Diagnostics;

//namespace Mbs.Collections
//{
   
//    [Serializable]
//    [DebuggerTypeProxy(typeof(DebuggerEnumerableView<>))]
//    public class PriorityQueue<T> : IQueue<T> where T : IComparable<T>
//    {
//        [NonSerialized]
//        private T[] heap;
//        [NonSerialized]
//        private int maxSize;
//        [NonSerialized]

//        private readonly object InnerLocker = new object();

//        public object SyncRoot { get { return InnerLocker; } }

//        public virtual bool IsSynchronized { get { return false; } }

//        public PriorityQueue() : this(10) { }
//        public PriorityQueue(int maxSize)
//        {
//            Count = 0;
//            int heapSize = maxSize + 1;
//            heap = new T[heapSize];
//            this.maxSize = maxSize;
//        }

//        private static bool LessThan(T a, T b)
//        {
//            return a.CompareTo(b) < 0;
//        }

//        private static int URShift(int number, int bits)
//        {
//            if (number >= 0)
//                return number >> bits;
//            else
//                return (number >> bits) + (2 << ~bits);
//        }

//        public bool Contains(T item)
//        {
//            if (Count < 1)
//                return false;
//            for (int i = 0; i < Count; i++)
//            {
//                if (object.Equals(heap[i], item))
//                    return true;
//            }
//            return false;
//        }

//        private void InternalPut(T item)
//        {
//            Count++;
//            heap[Count] = item;
//            UpHeap();
//        }

//        public void Enqueue(T item)
//        {
//            if (Count < maxSize - 1)
//            {
//                InternalPut(item);
//            }
//            else if (Count > 0 && !LessThan(item, Peek()))
//            {
//                heap[1] = item;
//                AdjustTop();
//            }
//            else
//            {
//                maxSize *= 2;
//                Array.Resize<T>(ref heap, maxSize);
//                InternalPut(item);
//            }
//        }

//        public T Peek()
//        {
//            if (Count > 0)
//                return heap[1];
//            else
//                return default(T);
//        }

//        public T Dequeue()
//        {
//            if (Count > 0)
//            {
//                T result = heap[1]; // save first value
//                heap[1] = heap[Count]; // move last to first
//                heap[Count] = default(T); // permit GC of objects
//                Count--;
//                DownHeap(); // adjust heap
//                return result;
//            }
//            else
//                return default(T);
//        }

//        /**/
//        /// <summary>Should be called when the Object at top changes values.  Still log(n)
//        /// worst case, but it's at least twice as fast to <pre>
//        /// { pq.top().change(); pq.adjustTop(); }
//        /// </pre> instead of <pre>
//        /// { o = pq.pop(); o.change(); pq.push(o); }
//        /// </pre>
//        /// </summary>
//        public void AdjustTop()
//        {
//            DownHeap();
//        }


//        public int Count { get; private set; }

//        public void Clear()
//        {
//            for (int i = 0; i <= Count; i++)
//                heap[i] = default(T);
//            Count = 0;
//        }

//        private void UpHeap()
//        {
//            int i = Count;
//            T node = heap[i]; // save bottom element
//            int j = URShift(i, 1);
//            while (j > 0 && LessThan(node, heap[j]))
//            {
//                heap[i] = heap[j]; // shift parents down
//                i = j;
//                j = URShift(j, 1);
//            }
//            heap[i] = node; // install saved element
//        }

//        private void DownHeap()
//        {
//            int i = 1;
//            T node = heap[i]; // save top element
//            int j = i << 1; // find smaller child
//            int k = j + 1;
//            if (k <= Count && LessThan(heap[k], heap[j]))
//            {
//                j = k;
//            }
//            while (j <= Count && LessThan(heap[j], node))
//            {
//                heap[i] = heap[j]; // shift up child
//                i = j;
//                j = i << 1;
//                k = j + 1;
//                if (k <= Count && LessThan(heap[k], heap[j]))
//                {
//                    j = k;
//                }
//            }
//            heap[i] = node; // install saved element
//        }

       

//        public static IQueue<T> Synchronized(IQueue<T> innerQueue)
//        {
//            return new SynPriorityQueue(innerQueue);
//        }

//        #region IEnumerable<TTarget> Members

//        public IEnumerator<T> GetEnumerator()
//        {
//            if (Count > 0)
//                foreach (var item in heap)
//                    yield return item;
//        }

//        #endregion

//        #region IEnumerable Members

//        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
//        {
//            return GetEnumerator();
//        }

//        #endregion

//        private class SynPriorityQueue : IQueue<T>
//        {
//            private IQueue<T> InnerQueue;
//            public SynPriorityQueue(IQueue<T> queue)
//            {
//                InnerQueue = queue;
//            }



//            #region IPriortyQueue<TMessage> Members

//            public void Enqueue(T item)
//            {
//                lock (InnerQueue.SyncRoot)
//                    InnerQueue.Enqueue(item);
//            }

//            public T Dequeue()
//            {
//                lock (InnerQueue.SyncRoot)
//                    return InnerQueue.Dequeue();
//            }

//            public T Peek()
//            {
//                return InnerQueue.Peek();
//            }

//            public int Count
//            {
//                get
//                {
//                    return InnerQueue.Count;
//                }
//            }

//            public void Clear()
//            {
//                lock (InnerQueue.SyncRoot)
//                    InnerQueue.Clear();
//            }

//            public bool Contains(T item)
//            {
//                lock (InnerQueue.SyncRoot)
//                    return InnerQueue.Contains(item);
//            }

//            public object SyncRoot
//            {
//                get { return InnerQueue.SyncRoot; }
//            }

//            public bool IsSynchronized
//            {
//                get { return true; }
//            }

//            #endregion

//            #region IEnumerable<TTarget> Members

//            public IEnumerator<T> GetEnumerator()
//            {
//                lock (InnerQueue.SyncRoot)
//                    return InnerQueue.GetEnumerator();
//            }

//            #endregion

//            #region IEnumerable Members

//            System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
//            {
//                return GetEnumerator();
//            }

//            #endregion
//        }
//    }
//}
